package cn.zifangsky.dp.questions;

import org.junit.Test;

import java.util.Random;

/**
 * 矩阵的最小路径和
 * <p>给定一个矩阵 m，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有的路径中最小的路径和。</p>
 *
 * @author zifangsky
 * @date 2020/5/22
 * @since 1.0.0
 */
public class Problem_001_MinPathSum {

    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        //1. 生成一个用于测试的随机数组
        int[][] arr = this.generateRandomMatrix(10, 7);
        //2. 遍历输出数组元素
        this.toString(arr);
        //3. 计算当前矩阵的最小路径和
        System.out.println("当前矩阵的最小路径和是：" + minPathSum1(arr));
        System.out.println("当前矩阵的最小路径和是：" + minPathSum2(arr));
    }

    /**
     * 解法一：
     * <ol>
     *     <li>从第一行的位置(0, 0)开始，分别计算从位置(0, 0)到位置(i, j)的最短路径和</li>
     *     <li>其中：minPathSum[i][j] = Min{minPathSum[i][j-1], minPathSum[i-1][j]} + arr[i][j]</li>
     *     <li>所以，只要依次求出矩阵中每个位置的最小路径和，最右下角的值即为整个问题的答案。</li>
     * </ol>
     *
     * @param arr 原始数组
     */
    private int minPathSum1(int[][] arr){
        if(arr == null || arr.length < 1 || arr[0] == null || arr[0].length < 1){
            throw new IllegalArgumentException("参数存在异常！");
        }

        int row = arr.length;
        int col = arr[0].length;
        int[][] dp = new int[row][col];

        //1. 从第一行的位置(0, 0)开始，分别计算从位置(0, 0)到位置(i, j)的最短路径和
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                //到达位置(i, j)之前一个位置的最短路径和
                int preMinPathSum = 0;

                //arr[0][0]
                if(i == 0 && j == 0){
                    preMinPathSum = 0;
                }
                //第一行的情况
                else if(i == 0){
                    preMinPathSum = dp[i][j-1];
                }
                //第一列的情况
                else if(j == 0){
                    preMinPathSum = dp[i-1][j];
                }
                //矩阵其他位置
                else{
                    preMinPathSum = Math.min(dp[i][j-1], dp[i-1][j]);
                }

                //求位置(i, j)的最短路径和
                dp[i][j] = preMinPathSum + arr[i][j];
            }
        }

        //2. 返回问题答案，即：位置(row-1, col-1)的最短路径和
        return dp[row-1][col-1];
    }

    
    /**
     * 解法二：
     * <p>解法二的思路跟解法一一致，但是还可以压缩空间，使用一个一维数组存储每一行/列的最短路径和即可</p>
     * <ol>
     *     <li>对于<b> row >= col </b>的情况，从左往右横向滚动过去</li>
     *     <li>对于<b> row < col </b>的情况，从上往下纵向滚动过去</li>
     * </ol>
     *
     * @param arr 原始数组
     */
    private int minPathSum2(int[][] arr){
        if(arr == null || arr.length < 1 || arr[0] == null || arr[0].length < 1){
            throw new IllegalArgumentException("参数存在异常！");
        }

        int row = arr.length;
        int col = arr[0].length;

        //用于标识（row >= col）或者（row < col）
        boolean rowMore = (row >= col);
        int more = (rowMore ? row : col);
        int less = (rowMore ? col : row);
        int[] dp = new int[less];

        //1. 从第一行的位置(0, 0)开始，分别计算从位置(0, 0)到位置(i, j)的最短路径和
        for(int i = 0; i < more; i++){
            for(int j = 0; j < less; j++){
                //到达位置(i, j)之前一个位置的最短路径和
                int preMinPathSum = 0;

                //arr[0][0]
                if(i == 0 && j == 0){
                    preMinPathSum = 0;
                }
                //rowMore ? 第一行的情况 : 第一列的情况
                else if(i == 0){
                    preMinPathSum = dp[j-1];
                }
                //rowMore ? 第一列的情况 : 第一行的情况
                else if(j == 0){
                    preMinPathSum = dp[0];
                }
                //矩阵其他位置
                else{
                    preMinPathSum = Math.min(dp[j-1], dp[j]);
                }

                //求位置(i, j)的最短路径和
                if(rowMore){
                    dp[j] = preMinPathSum + arr[i][j];
                }else{
                    dp[j] = preMinPathSum + arr[j][i];
                }
            }
        }

        //2. 返回问题答案，即：位置(row-1, col-1)的最短路径和
        return dp[less-1];
    }


    /**
     * 生成随机整型矩阵
     * @param row 行
     * @param col 列
     * @return int[][]
     */
    private int[][] generateRandomMatrix(int row, int col){
        if(row < 1 || col < 1){
            throw new IllegalArgumentException("参数存在异常！");
        }

        Random rnd = new Random();
        int[][] arr = new int[row][col];

        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                arr[i][j] = rnd.nextInt(20);
            }
        }

        return arr;
    }

    /**
     * 遍历输出数组元素
     */
    private void toString(int[][] arr){
        if(arr == null || arr.length < 1 || arr[0] == null || arr[0].length < 1){
            throw new IllegalArgumentException("参数存在异常！");
        }

        int row = arr.length;
        int col = arr[0].length;

        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }

}
